Data Structure
Q61.
Postorder traversal of a given binary search tree, T produces the following sequence of keys 10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29 Which one of the following sequences of keys can be the result of an in-order traversal of the tree T?Q63.
The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?Q64.
Let T(n) be the number of different binary search trees on n distinct elements. Then T(n)=\sum_{k=1}^{n}T(k-1)T(x), where x isQ65.
Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the inorder transversal sequence of the resultant tree ?Q66.
The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?Q67.
A binary search tree is generated by inserting in order the following integers: 50,15,62,5,20,58,91,3,8,37,60,24 The number of nodes in the left subtree and right subtree of the root respectively isQ69.
In a balanced binary search tree with n elements, what is the worst case time complexity of reporting all elements in range [a,b]? Assume that the number of reported elements is k.Q70.
What is the worst case time complexity of inserting n^2 elements into an AVL-tree with n elements initially?